#ifndef BIN_H_
#define BIN_H_

#include <algorithm>
#include <cstdint>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>

namespace
{

constexpr size_t BASE = 10;
// 返回number在BASE进制下有几位
template<class T, std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char>, int> = 0>
inline constexpr size_t bits(T number)
{
    size_t ans = 0;
    while (number > 0) {
        number /= BASE;
        ans++;
    }
    return ans;
}

// 基数排序核心代码
// 数据必须为非负整数
// bits是元素中最大值在BASE进制下有几位
template<class T, std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char>, int> = 0>
inline void r_sort(T* arr, size_t size, size_t bits)
{
    std::vector<T> help(size);
    size_t         cnt[BASE] = {};
    for (size_t offst = 1; bits > 0; offst *= BASE, bits--) {
        for (auto& i : cnt) {
            i = 0;
        }
        for (auto p = arr; p != arr + size; p++) {
            cnt[(*p / offst) % BASE]++;
        }
        for (int i = 1; i < BASE; i++) {
            cnt[i] = cnt[i] + cnt[i - 1];
        }

        for (int i = size - 1; i >= 0; i--) {
            const size_t index = --cnt[(*(arr + i) / offst) % BASE];
            help[index]        = *(arr + i);
        }
        for (T *p1 = arr, *p2 = help.data(); p1 != arr + size; p1++, p2++) {
            *p1 = *p2;
        }
    }
}

// 基数排序对数据有要求
// 必须为整数
template<class T, std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char>, int> = 0>
inline void radix_sort(T* arr, size_t size)
{
    if (size == 0) return;
    T min = *std::min_element(arr, arr + size);
    for (T* p = arr; p != arr + size; p++) {
        *p -= min;
    }
    T max = *std::max_element(arr, arr + size);
    r_sort(arr, size, bits(max));
    for (T* p = arr; p != arr + size; p++) {
        *p += min;
    }
}
}   // namespace

namespace lxj
{
// 爱吃香蕉的珂珂
// 珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉
// 警卫已经离开了，将在 h 小时后回来。
// 珂珂可以决定她吃香蕉的速度 k （单位：根/小时)
// 每个小时，她将会选择一堆香蕉，从中吃掉 k 根
// 如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉
// 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
// 返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）
// 测试链接 : https://leetcode.cn/problems/koko-eating-bananas/
inline int minEatingSpeed(std::vector<int>& piles, int h)
{
    auto duration = [&piles](int speed) {
        int64_t d = 0;
        for (auto i : piles) {
            d += (i + speed - 1) / speed;
        }
        return d;
    };
    int l = 1, r = *std::max_element(piles.cbegin(), piles.cend());
    int ans = 0;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (duration(m) <= h) {
            ans = m;
            r   = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return ans;
}

// 分割数组的最大值(画匠问题)
// 给定一个非负整数数组 nums 和一个整数 m
// 你需要将这个数组分成 m 个非空的连续子数组。
// 设计一个算法使得这 m 个子数组各自和的最大值最小。
// 测试链接 : https://leetcode.cn/problems/split-array-largest-sum/
inline int splitArray(std::vector<int>& nums, int k)
{
    auto f = [&nums](int64_t limit) {
        int64_t part = 1, sum = 0;
        for (auto num : nums) {
            if (num > limit) {
                return (int64_t) ~(1 << 31);
            }
            if (sum + num > limit) {
                part++;
                sum = num;
            }
            else {
                sum += num;
            }
        }
        return part;
    };

    int64_t ans = 0;
    for (int64_t l = 0, r = std::accumulate(nums.cbegin(), nums.cend(), 0), m, need; l <= r;) {
        m    = l + (r - l) / 2;
        need = f(m);
        if (need <= k) {
            ans = m;
            r   = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return (int)ans;
}

// 机器人跳跃问题
// 机器人正在玩一个古老的基于DOS的游戏
// 游戏中有N+1座建筑，从0到N编号，从左到右排列
// 编号为0的建筑高度为0个单位，编号为i的建筑的高度为H(i)个单位
// 起初机器人在编号为0的建筑处
// 每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E
// 下一步它将跳到第个k+1建筑
// 它将会得到或者失去正比于与H(k+1)与E之差的能量
// 如果 H(k+1) > E 那么机器人就失去H(k+1)-E的能量值，否则它将得到E-H(k+1)的能量值
// 游戏目标是到达第个N建筑，在这个过程中，能量值不能为负数个单位
// 现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏
// 测试链接 : https://www.nowcoder.com/practice/7037a3d57bbd4336856b8e16a9cafd71
inline int robotPassThroughBuilding(const std::vector<int>& buildings)
{
    auto goall = [&buildings](int64_t energy, int64_t max) {
        for (auto i : buildings) {
            energy >= i ? energy += energy - i : energy -= i - energy;
            if (energy >= max) return true;
            if (energy < 0) return false;
        }
        return true;
    };
    int64_t l = 0, max = *std::max_element(buildings.cbegin(), buildings.cend()), r = max;
    int64_t ans = 0;
    for (int64_t m; l <= r;) {
        m = l + (r - l) / 2;
        if (goall(m, max)) {
            ans = m;
            r   = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return (int)ans;
}

// 找出第K小的数对距离
// 数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
// 给你一个整数数组 nums 和一个整数 k
// 数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length
// 返回 所有数对距离中 第 k 小的数对距离。
// 测试链接 : https://leetcode.cn/problems/find-k-th-smallest-pair-distance/
inline int smallestDistancePair(std::vector<int>& nums, int k)
{
    auto f = [&nums](int limit) {
        int ans = 0;
        for (int l = 0, r = 0; l < nums.size(); l++) {
            while (r + 1 < nums.size() && nums[r + 1] - nums[l] <= limit) r++;
            ans += r - l;
        }
        return ans;
    };
    int len = nums.size();
    radix_sort(nums.data(), len);
    int ans = 0;
    for (int l = 0, r = nums[len - 1] - nums[0], m, cnt; l <= r;) {
        m   = l + (r - l) / 2;
        cnt = f(m);
        if (cnt >= k) {
            ans = m;
            r   = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return ans;
}

// 同时运行N台电脑的最长时间
// 你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries
// 其中第 i 个电池可以让一台电脑 运行 batteries[i] 分钟
// 你想使用这些电池让 全部 n 台电脑 同时 运行。
// 一开始，你可以给每台电脑连接 至多一个电池
// 然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，并连接另一个电池，你可以进行这个操作
// 任意次 新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池
// 断开连接和连接新的电池不会花费任何时间。
// 注意，你不能给电池充电。
// 请你返回你可以让 n 台电脑同时运行的 最长 分钟数。
// 测试链接 : https://leetcode.cn/problems/maximum-running-time-of-n-computers/
/*方法一: 范围大，未剪枝，不精细*/
inline long long maxRunTime1(std::vector<int>& batteries, int n)
{
    auto f = [&batteries](int num, unsigned long long time) {
        unsigned long long sum = 0;
        for (int x : batteries) {
            if (x > time) {
                num--;
            }
            else {
                sum += x;
            }
            if (sum >= (unsigned long long)num * time) return true;
        }
        return false;
    };
    unsigned long long l = 0, m = 0,
                       r   = std::accumulate(batteries.cbegin(), batteries.cend(), 0ull);
    unsigned long long ans = 0;
    while (l <= r) {
        m = l + (r - l) / 2;
        if (f(n, m)) {
            ans = m;
            l   = m + 1;
        }
        else {
            r = m - 1;
        }
    }
    return ans;
}
/*方法二: 二分答案法 + 增加分析(贪心)*/
inline long long maxRunTime2(std::vector<int>& batteries, int n)
{
    int                max = 0;
    unsigned long long sum = 0;
    for (auto i : batteries) {
        max = std::max(max, i);
        sum += i;
    }
    // 所有电池的最大电量是max
    // 如果此时sum > (long) max * num，
    // 说明 : 最终的供电时间一定在 >= max，而如果最终的供电时间 >= max
    // 说明 : 对于最终的答案X来说，所有电池都是课上讲的"碎片拼接"的概念
    // 那么寻找 ? * num <= sum 的情况中，尽量大的 ? 即可
    // 即sum / num
    if (sum > (unsigned long long)max * n) return sum / n;
    // 最终的供电时间一定在 < max范围上
    // [0, sum]二分范围，可能定的比较粗，虽然不影响，但毕竟是有点慢
    // [0, max]二分范围！更精细的范围，二分次数会变少
    auto f = [&batteries](int num, int time) {
        long long sum = 0;
        for (int x : batteries) {
            x > time ? num-- : sum += x;
            if (sum >= (long long)time * num) return true;
        }
        return false;
    };
    int ans = 0;
    for (int l = 0, r = max, m; l <= r;) {
        m = l + (r - l) / 2;
        if (f(n, m)) {
            ans = m;
            l   = m + 1;
        }
        else {
            r = m - 1;
        }
    }
    return ans;
}

// 计算等位时间
// 给定一个数组arr长度为n，表示n个服务员，每服务一个人的时间
// 给定一个正数m，表示有m个人等位，如果你是刚来的人，请问你需要等多久？
// 假设m远远大于n，比如n <= 10^3, m <= 10^9，该怎么做是最优解？
// 谷歌的面试，这个题连考了2个月
// 找不到测试链接，所以用对数器验证
inline int waitingTime1(const std::vector<int>& arr, int m)
{
    auto comp = [](const std::pair<long long, int>& p1, const std::pair<long long, int>& p2) {
        return p1.first > p2.first;
    };
    std::priority_queue<std::pair<long long, int>,
                        std::vector<std::pair<long long, int>>,
                        decltype(comp)>
        heap(comp);
    for (auto i : arr) {
        heap.push({0, i});
    }
    for (int i = 0; i < m; i++) {
        auto p = heap.top();
        heap.pop();
        p.first += p.second;
        heap.push(p);
    }
    return heap.top().first;
}
// 二分答案法
// 最优解
// 时间复杂度O(n * log(min * w))，额外空间复杂度O(1)
inline int waitingTime2(const std::vector<int>& arr, int w)
{
    auto f = [&arr](int time) {
        int sum = 0;
        for (int x : arr) {
            sum += (time / x) + 1;
        }
        return sum;
    };
    int min = *std::min_element(arr.cbegin(), arr.cend());
    int ans = 0;
    for (int l = 0, r = min * w, m; l <= r;) {
        m = l + (r - l) / 2;
        if (f(m) >= w + 1) {
            ans = m;
            r   = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return ans;
}

// 刀砍毒杀怪兽问题
// 怪兽的初始血量是一个整数hp，给出每一回合刀砍和毒杀的数值cuts和poisons
// 第i回合如果用刀砍，怪兽在这回合会直接损失cuts[i]的血，不再有后续效果
// 第i回合如果用毒杀，怪兽在这回合不会损失血量，但是之后每回合都损失poisons[i]的血量
// 并且你选择的所有毒杀效果，在之后的回合都会叠加
// 两个数组cuts、poisons，长度都是n，代表你一共可以进行n回合
// 每一回合你只能选择刀砍或者毒杀中的一个动作
// 如果你在n个回合内没有直接杀死怪兽，意味着你已经无法有新的行动了
// 但是怪兽如果有中毒效果的话，那么怪兽依然会在血量耗尽的那回合死掉
// 返回至少多少回合，怪兽会死掉
// 数据范围 :
// 1 <= n <= 10^5
// 1 <= hp <= 10^9
// 1 <= cuts[i]、poisons[i] <= 10^9
// 本题来自真实大厂笔试，找不到测试链接，所以用对数器验证
inline int cutOrPoison(std::vector<int>& cnts, std::vector<int>& poisons, long long hp)
{
    auto f = [&cnts, &poisons](int limit, long long hp) {
        int n = std::min((int)cnts.size(), limit);
        for (int i = 0, j = 1; i < n; i++, j++) {
            hp -= std::max((long long)cnts[i], (long long)(limit - j) * (long long)poisons[i]);
            if (hp <= 0) return true;
        }
        return false;
    };
    int ans = ~(1 << 31);
    for (int l = 1, r = hp + 1, m; l <= r;) {
        m = l + (r - l) / 2;
        if (f(m, hp)) {
            ans = m;
            r   = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return ans;
}
}   // namespace lxj

#endif